package chart;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.Edge;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 拓扑排序
 * 只针对有向无环图
 * 实现方式：栈(或队列)、深度优先搜索(即 DFS)
 *
 * @author yezh
 * @date 2024/9/12 17:49
 */
public class TopologicalSort {

    public static void main(String[] args) {
        Edge e1 = new Edge(0, 1, 2);
        Edge e2 = new Edge(0, 2, 3);
        Edge e3 = new Edge(0, 5, 1);
        Edge e4 = new Edge(1, 3, 1);
        Edge ex = new Edge(1, 2, 1);
        Edge e5 = new Edge(1, 4, 1);
        Edge e6 = new Edge(2, 3, 1);
        Edge e7 = new Edge(2, 5, 1);
        Edge e8 = new Edge(3, 4, 1);
        Edge e9 = new Edge(3, 5, 1);
        Edge e10 = new Edge(4, 5, 1);
        List<Edge> edges = Arrays.asList(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10);

        AbstractGraph graph = new AdjacencyMatrix(6, true);
        graph.createGraph(edges);
        doWithBFS(graph);
        System.out.println();
        doWithDFS(graph);
    }

    /**
     * 无前驱顶点优先
     *
     * @param graph
     */
    public static void doWithBFS(AbstractGraph graph) {
        int n = graph.getV();
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++)
            for (Integer neighborVertex : graph.getNeighborVertex(i))
                inDegree[neighborVertex]++;

        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < n; i++) if (inDegree[i] == 0) st.push(i);
        while (!st.isEmpty()) {
            int vertex = st.pop();
            System.out.print(vertex + " ");
            for (Integer neighborVertex : graph.getNeighborVertex(vertex))
                if (--inDegree[neighborVertex] == 0) st.push(neighborVertex);
        }
    }

    static int idx;
    static int[] times;

    /**
     * 无后继顶点优先
     *
     * @param graph
     */
    public static void doWithDFS(AbstractGraph graph) {
        idx = 0;
        int v = graph.getV();
        times = new int[v];
        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) if (!visited[i]) dfs(i, visited, graph);
        for (int i = v - 1; i >= 0; i--) System.out.print(times[i] + " ");
    }

    private static boolean dfs(int vertex, boolean[] visited, AbstractGraph graph) {
        visited[vertex] = true;
        for (Edge edge : graph.getNeighborEdge(vertex))
            // 相邻的顶点已经被访问过, 现在又要被访问, 说明有环; 相邻顶点返回 false, 则直接返回 false
            if (visited[edge.getArcHead()] || !dfs(edge.getArcHead(), visited, graph)) return false;
        times[idx++] = vertex;
        return true;
    }

}
